package src;// St�rikerfi 2, H�sk�linn � Reykjav�k.
//
// Optimal s��uskiptareiknirit.  �tf�rt me� heilt�lufylki.  Ef reynt a�
// b�ta vi� s��u �egar fylki er fullt er valin �t s��a til a� skipta skv, optimal.
// Finnum �� s��u sem er lengst �anga� til a� ver�i notu� aftur e�a ver�ur aldrei 
// notu� aftur og skiptum henni �t. 
//
// �lafur Ragnar Helgason (c), febr�ar 2002


import java.io.*;
import java.util.*;

public class OptimalMem {

  public OptimalMem(int memSize)
  {
    mem = new int[memSize];
    for (int i = 0; i < mem.length; i++)
      mem[i] = -1;
    usedMem = 0;
  } 

  public void update(int memString[], int strIdx) 
  {
    if (usedMem == mem.length) {
      replaceOutVictim(memString, strIdx);
    } else {
      mem[usedMem] = memString[strIdx];
      usedMem++;
    }
  }

  private void replaceOutVictim(int memString[], int strIdx) 
  {
    int victimIdx = -1, longestNextUsed = -1, untilNextUsed;
    for (int i = 0; i < mem.length; i++) {
      untilNextUsed = -1;
      for (int j = strIdx + 1; j < memString.length; j++) {
        if (memString[j] == mem[i]) {
          untilNextUsed = j - strIdx;
          if (untilNextUsed > longestNextUsed) {
            victimIdx = i;
            longestNextUsed = untilNextUsed;
          }
          break;
        }
      }
      if (untilNextUsed == -1)  // Page never used again, swap out
      {
        victimIdx = i;
        break;
      }
    }
    mem[victimIdx] = memString[strIdx];
  }

  public boolean contains(int page) 
  {
    for (int i = 0; i < mem.length; i++) {
      if (mem[i] == page)
        return true;
    }
    return false;
  }

  private int mem[];
  private int usedMem;
}
